package com.cat.dynamicPlanning02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-string-chain/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/11/3 20:03
 * @since JDK17
 */

public class Solution27 {
    boolean check(String s1, String s2) {
        if (s2.length() != s1.length() + 1) {
            return false;
        }
        boolean flag = false;
        for (int i = 0, j = 0; i < s1.length(); i++, j++) {
            if (s1.charAt(i) != s2.charAt(j)) {
                if (!flag) {
                    flag = true;
                    i--;
                } else {
                    return false;
                }
            }
        }

        return true;
    }
    public int longestStrChain(String[] words) {
        int n = words.length;
        int[] dp = new int[n];
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (check(words[j], words[i])) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}
